//给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
//
// 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
//
//
//
// 例如，在下面的 3×4 的矩阵中包含单词 "ABCCED"（单词中的字母已标出）。
//
//
//
//
//
// 示例 1：
//
//
//输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word =
//"ABCCED"
//输出：true
//
//
// 示例 2：
//
//
//输入：board = [["a","b"],["c","d"]], word = "abcd"
//输出：false
//
//
//
//
// 提示：
//
//
// m == board.length
// n = board[i].length
// 1 <= m, n <= 6
// 1 <= word.length <= 15
// board 和 word 仅由大小写英文字母组成
//
//
// 注意：本题与主站 79 题相同：https://leetcode-cn.com/problems/word-search/
//
// Related Topics 数组 回溯 矩阵 👍 802 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function exist(board: string[][], word: string): boolean {

    function backtracking(i,j,t) {
        if (t >= word.length) return true
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] !== word[t] || board[i][j] == "#") {
            return false
        }
        let temp = board[i][j]
        board[i][j] = '#'
        let res =
            backtracking(i + 1,j,t + 1) ||
            backtracking(i - 1,j,t + 1) ||
            backtracking(i,j + 1,t + 1) ||
            backtracking(i,j - 1,t + 1)
        if (res) return true;
        //? 如果不是true则需要回溯回去了
        board[i][j] = temp
        return false
    }

    for (let i = 0 ;i < board.length; i ++) {
        for (let j = 0; j < board[0].length; j ++) {
            if (word[0] === board[i][j]) {
                let res = backtracking(i,j,0)
                if (res) return true
            }
        }
    }
    return false
};
//leetcode submit region end(Prohibit modification and deletion)
